모든 경우의 수를 따져야 할 때가 있다.

하지만 무식하게 모든 경우를 따져서 문제가 풀릴거면 문제가 왜있겠는가?

좀더 똑똑하게 모든 경우를 따져보자

BackTracking

BackTracking은 기본적으로 DFS를 하여 모든 분기를 따져보는 것이다. 중요한점은 두가지이다.

방법

1. 분기가 나누어질때 문제 조건에 따라 가지치기를 한다.
2. 뒤로 돌아갈때 바꾼 변수 등을 원래대로 되돌린다.

시간복잡도

BackTracking의 시간복잡도는 최악의 경우 $O(b^N)$이다.

b는 각 단계에서 분기하는 경우의 수, N은 문제의 크기이다.

(N-Queen 문제의 경우, queen을 두기/안두기 → b = 2, 체스판의 크기 nn → N = nn)

깨달음

• 시간 복잡도가 크므로, 가지치기를 최대한 해야한다.
• 또는 문제를 나누는 것도 방법이다. N이 커질수록 걸리는 시간이 기하급수적으로 증가하므로, 가능하다면 O(b^(N/2) + b^(N/2)) 따위로 줄일수 있다면 최고다. (N-Bishop 문제의 경우, 체스판을 흑/백으로 나누어 문제의 크기가 절반인 두 문제로 쪼갤수 있다.)

N개의 후보군 중 찾아야 하는 요소를 log(N)의 시간복잡도로 찾는다.

Binary Search

방법

1. 상한과 하한을 지정하고, 상한과 하한이 맞닿을 때까지 반복을 수행한다.
2. 루프 내에서는,
   1. 상한과 하한의 중앙값을 계산한다.
   2. 목표치를 문제에 맞게 계산한다.
3. 상한과 하한을 갱신한다.
   1. 중앙값이 목표치보다 클 경우, 상한을 중앙값으로 설정한다.
   2. 중앙값이 목표치보다 작을 경우, 하한을 중앙값으로 설정한다.
   3. 중앙값이 목표치와 같을 경우, 루프를 종료한다.

주의점

• 상한과 하한의 초기값을 명확하게 지정해야한다, 더 좁은 범위를 지정해서는 안된다. but, 상한 두배 → 루프 1회 추가이므로 더 넓은 범위는 거의 상관없다.
• 루프를 도는 횟수가 log(N)이므로, 루프 안에서 어떤 계산을 할지 고려해야 한다. → 요소를 다 탐색하면 Nlog(N)의 시간 복잡도를 가진다.
• 문제의 조건에 맞게 상한과 하한을 갱신하여야 한다. → 목표치와 같다고 루프를 종료해서는 안될 때도 있다.